def _related_pos(i,j):
	rs = []
	rs.append([(i,k) for k in range(9) if k!=j])
	rs.append([(k,j) for k in range(9) if k!=i])
	if i==j:
		rs.append([(k,k) for k in range(9) if k!=i])
	if (i+j)==8:
		rs.append([(k,8-k) for k in range(9) if k!=i])
	gi,gj = i//3,j//3
	rs.append([((gi*3)+ki, (gj*3)+kj) 
				for ki in range(3) 
				for kj in range(3)
				if not ((((gi*3)+ki)==i) and (((gj*3)+kj)==j))])
	return rs

_related_pos_cache = {}
def related_pos(i,j):
	if (i,j) not in _related_pos_cache:
		_related_pos_cache[(i,j)] = _related_pos(i,j)
	return _related_pos_cache[(i,j)]

def valid_values(d,i,j):
	rs = related_pos(i,j)
	invalid = set()
	for r in rs:
		for ri,rj in r:
			if d[ri][rj]==0: continue
			invalid.add(d[ri][rj])
	return sorted({i+1 for i in range(9)}-invalid)

class Sudoku:
	solutions_ = []
	max_solutions = 2
	print_details = False

	def _fill(self):
		valids = []
		changed = False
		for i in range(9):
			for j in range(9):
				if self.d[i][j]>0: continue
				valid = valid_values(self.d,i,j)
				assert len(valid)>0, (i,j)
				if len(valid)==1:
					self.d[i][j] = valid[0]
					changed = True
				else:
					valids.append((i,j,valid))
		return changed, valids

	def __init__(self, d, depth=0, history=None):
		if history is None:
			history = []
		self.depth = depth
		self.d = d
		self.history = history
		if (len(history)>0) and Sudoku.print_details:
			print()
			print('  '*self.depth,'暂定:', ', '.join([f'位置{(i,j)}是{v}' for i,j,v in history]))

	def _search(self):
		import copy
		while True:
			changed, valids = self._fill()
			if changed:
				continue
			if (len(valids)==0): # done
				if Sudoku.print_details:
					print('  '*self.depth,'===== 完成 ======')
					Sudoku.print(self.d, self.depth
						)
				Sudoku.solutions_.append([self.history, self.d])
				return True 
			else:
				i,j,vs = valids[0]
				if Sudoku.print_details:
					print('  '*self.depth,f'暂时无法确定所有值,接下来可在{(i,j)}尝试这些值:{vs}')
				for v in vs:
					d = copy.deepcopy(self.d)
					d[i][j] = v
					history = copy.deepcopy(self.history)
					history.append([i,j,v])
					s = None
					try: 
						s = Sudoku(d, self.depth+1, history)
						s._search()
						if len(Sudoku.solutions_)>=Sudoku.max_solutions:
							return True
					except AssertionError as ex:
						if Sudoku.print_details:
							print('  '*self.depth,f'  -- 在{ex}失败--')
							Sudoku.print(s.d, s.dept)
				return False
		return False

	def print(d, depth=0, empty='_'):
		repr = ''
		for i in range(9):
			repr = repr + (('  '*depth)+('[[' if i==0 else ' ['))
			for j in range(9):
				repr = repr + ((empty if d[i][j]==0 else str(d[i][j]))+('' if j==8 else ','))
			repr = repr + (']]\n' if i==8 else '],\n')
		print(repr)

	def search(d):
		Sudoku.solutions_.clear()
		Sudoku(d)._search()
		return Sudoku.solutions_

	def report(d):
		solutions = Sudoku.search(d)
		if len(solutions)==0:
			print('无解')
		else:
			for i,[h,d] in enumerate(solutions):
				print(f'\n ===== 答案{i+1} =====')
				print(' 设定',', '.join([f'位置{(i,j)}是{v}' for i,j,v in h]))
				Sudoku.print(d)


# import sudoku
# Sudoku = sudoku.Sudoku
# print('要所有可能的解答吗？[y/N]',end='')
# Sudoku.max_solutions = (1000 if input()=='y' else 2)
# print('要看解答步骤吗？[y/N]',end='')
# Sudoku.print_details = (input()=='y')
# Sudoku.report(d0)
